Search Results

Documents authored by Pashkovich, Kanstantsin

Document
DOI: 10.4230/LIPIcs.ITCS.2024.84
Budget-Feasible Mechanism Design: Simpler, Better Mechanisms and General Payment Constraints

Authors: Rian Neogi, Kanstantsin Pashkovich, and Chaitanya Swamy

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
In budget-feasible mechanism design, a buyer wishes to procure a set of items of maximum value from self-interested rational players. We are given an item-set U and a nonnegative valuation function v: 2^U ↦ ℝ_+. Each item e is held by a player who incurs a private cost c_e for supplying item e. The goal is to devise a truthful mechanism such that the total payment made to the players is at most some given budget B, and the value of the set returned is a good approximation to OPT: = max {v(S): c(S) ≤ B, S ⊆ U}. We call such a mechanism a budget-feasible mechanism. More generally, there may be additional side constraints requiring that the set returned lies in some downwards-monotone family ℐ ⊆ 2^U. Budget-feasible mechanisms have been widely studied, but there are still significant gaps in our understanding of these mechanisms, both in terms of what kind of oracle access to the valuation is required to obtain good approximation ratios, and the best approximation ratio that can be achieved. We substantially advance the state of the art of budget-feasible mechanisms by devising mechanisms that are simpler, and also better, both in terms of requiring weaker oracle access and the approximation factors they obtain. For XOS valuations, we devise the first polytime O(1)-approximation budget-feasible mechanism using only demand oracles, and also significantly improve the approximation factor. For subadditive valuations, we give the first explicit construction of an O(1)-approximation mechanism, where previously only an existential result was known. We also introduce a fairly rich class of mechanism-design problems that we dub using the umbrella term generalized budget-feasible mechanism design, which allow one to capture payment constraints that are much-more nuanced than a single constraint on the total payment doled out. We demonstrate the versatility of our ideas by showing that our constructions can be adapted to yield approximation guarantees in such general settings as well. A prominent insight to emerge from our work is the usefulness of a property called nobossiness, which allows us to nicely decouple the truthfulness + approximation, and budget-feasibility requirements. Some of our constructions can be viewed as reductions showing that an O(1)-approximation budget-feasible mechanism can be obtained provided we have a (randomized) truthful mechanism satisfying nobossiness that returns a (random) feasible set having (expected) value Ω(OPT).
Cite as

Rian Neogi, Kanstantsin Pashkovich, and Chaitanya Swamy. Budget-Feasible Mechanism Design: Simpler, Better Mechanisms and General Payment Constraints. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 84:1-84:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{neogi_et_al:LIPIcs.ITCS.2024.84,
  author =	{Neogi, Rian and Pashkovich, Kanstantsin and Swamy, Chaitanya},
  title =	{{Budget-Feasible Mechanism Design: Simpler, Better Mechanisms and General Payment Constraints}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{84:1--84:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.84},
  URN =		{urn:nbn:de:0030-drops-196128},
  doi =		{10.4230/LIPIcs.ITCS.2024.84},
  annote =	{Keywords: Algorithmic mechanism design, Approximation algorithms, Budget-feasible mechanisms}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.17
On the Integrality Gap of the Prize-Collecting Steiner Forest LP

Authors: Jochen Könemann, Neil Olver, Kanstantsin Pashkovich, R. Ravi, Chaitanya Swamy, and Jens Vygen

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
In the prize-collecting Steiner forest (PCSF) problem, we are given an undirected graph G=(V,E), nonnegative edge costs {c_e} for e in E, terminal pairs {(s_i,t_i)} for i=1,...,k, and penalties {pi_i} for i=1,...,k for each terminal pair; the goal is to find a forest F to minimize c(F) + sum{ pi_i: (s_i,t_i) is not connected in F }. The Steiner forest problem can be viewed as the special case where pi_i are infinite for all i. It was widely believed that the integrality gap of the natural (and well-studied) linear-programming (LP) relaxation for PCSF (PCSF-LP) is at most 2. We dispel this belief by showing that the integrality gap of this LP is at least 9/4 even if the input instance is planar. We also show that using this LP, one cannot devise a Lagrangian-multiplier-preserving (LMP) algorithm with approximation guarantee better than 4. Our results thus show a separation between the integrality gaps of the LP-relaxations for prize-collecting and non-prize-collecting (i.e., standard) Steiner forest, as well as the approximation ratios achievable relative to the optimal LP solution by LMP- and non-LMP-approximation algorithms for PCSF. For the special case of prize-collecting Steiner tree (PCST), we prove that the natural LP relaxation admits basic feasible solutions with all coordinates of value at most 1/3 and all edge variables positive. Thus, we rule out the possibility of approximating PCST with guarantee better than 3 using a direct iterative rounding method.
Cite as

Jochen Könemann, Neil Olver, Kanstantsin Pashkovich, R. Ravi, Chaitanya Swamy, and Jens Vygen. On the Integrality Gap of the Prize-Collecting Steiner Forest LP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{konemann_et_al:LIPIcs.APPROX-RANDOM.2017.17,
  author =	{K\"{o}nemann, Jochen and Olver, Neil and Pashkovich, Kanstantsin and Ravi, R. and Swamy, Chaitanya and Vygen, Jens},
  title =	{{On the Integrality Gap of the Prize-Collecting Steiner Forest LP}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{17:1--17:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.17},
  URN =		{urn:nbn:de:0030-drops-75665},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.17},
  annote =	{Keywords: Integrality gap, Steiner tree, Steiner forest, prize-collecting, Lagrangianmultiplier- preserving}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.33
Fast Approximation Algorithms for the Generalized Survivable Network Design Problem

Authors: Andreas Emil Feldmann, Jochen Könemann, Kanstantsin Pashkovich, and Laura Sanità

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
In a standard f-connectivity network design problem, we are given an undirected graph G = (V, E), a cut-requirement function f : 2^V to N, and non-negative costs c(e) for all e in E. We are then asked to find a minimum-cost vector x in N^E such that x(delta(S)) geq f (S) for all S subseteq V. We focus on the class of such problems where f is a proper function. This encodes many well-studied NP-hard problems such as the generalized survivable network design problem. In this paper we present the first strongly polynomial time FPTAS for solving the LP relaxation of the standard IP formulation of the f-connectivity problem with general proper functions f. Implementing Jain’s algorithm, this yields a strongly polynomial time (2 + epsilon)-approximation for the generalized survivable network design problem (where we consider rounding up of rationals an arithmetic operation).
Cite as

Andreas Emil Feldmann, Jochen Könemann, Kanstantsin Pashkovich, and Laura Sanità. Fast Approximation Algorithms for the Generalized Survivable Network Design Problem. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 33:1-33:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{feldmann_et_al:LIPIcs.ISAAC.2016.33,
  author =	{Feldmann, Andreas Emil and K\"{o}nemann, Jochen and Pashkovich, Kanstantsin and Sanit\`{a}, Laura},
  title =	{{Fast Approximation Algorithms for the Generalized Survivable Network Design Problem}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{33:1--33:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.33},
  URN =		{urn:nbn:de:0030-drops-68035},
  doi =		{10.4230/LIPIcs.ISAAC.2016.33},
  annote =	{Keywords: strongly polynomial runtime, generalized survivable network design, primal-dual method}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact